Алгоритм Ґровера

Алгоритм Ґровера (також GSA від англ. Grover search algorithm) — квантовий алгоритм вирішення задачі перебору, тобто пошуку рішення рівняння

$(1)\qquad f(x)=1,$

де $f$ є булева функція від $n$ змінних, а $x$ — двійковий вектор довжини $n$. Був запропонований американським математиком Ловом Ґровером в 1996 році.

Представлення алгоритму Ґровера

Передбачається, що функція задана у вигляді чорного ящика, або оракула, тобто в ході рішення ми можемо тільки задавати оракула питання типу: «чому дорівнює $f$ при даному $x$», І після отримання відповіді використовувати його в подальших обчисленнях. Тобто завдання вирішення рівняння (1) є загальною формою завдання перебору; тут потрібно знайти «пароль до пристрою $f$», Що класично вимагає прямого перебору всіх $N=2^{n}$ варіантів.

Алгоритм Ґровера знаходить деякий корінь рівняння, використовуючи ${\frac {\pi }{4}}{\sqrt {N}}$ звернень до функції $f$, з використанням $O(n)$ кубітів.

Сенс алгоритму Ґровера складається в «посиленні амплітуди» цільового стану за рахунок зменшення амплітуди всіх інших станів. Геометрично алгоритм Ґровера полягає в обертанні поточного вектора стану квантового комп'ютера у напрямку точно до цільового стану (рух по найкоротшому шляху забезпечує оптимальність алгоритму Ґровера). Кожен крок дає обертання на кут $2\alpha$, де кут між $I_{\tilde {0}}$ і  $I_{x_{tar}}$становить $\pi /2-\alpha$. Подальше продовження ітерацій оператора G дасть продовження обходу кола в речовій площині, породженої даними векторами.

Ґроверівське «посилення амплітуди» є, мабуть, фундаментальним фізичним феноменом в квантової теорії багатьох тіл. Наприклад, його облік необхідний для оцінки ймовірностей подій, які здаються «рідкісними». Процес, який реалізує схему алгоритму Ґровера, призводить до вибухового зростання спочатку знехтуваної малої амплітуди, що здатне швидко довести її до реально спостережуваних величин.

Застосування алгоритму

Хоча мета алгоритму Ґровера зазвичай описується як «пошук в базі даних», можна більш точно описати його як «інвертування функції». Насправді, так як «пророча машина» неструктурованої бази даних вимагає, хоча б лінійної складності, алгоритм не може бути використаний для реальних баз даних. Грубо кажучи, якщо функцію $y=f(x)$ можна оцінити на квантовому комп'ютері, алгоритм Ґровера обчислює $x$ за заданим $y$. Інверсія функція пов'язана з пошуком бази даних, тому що ми могли б придумати функцію, яка виробляє одне конкретне значення $y$ (наприклад «істинно»), якщо $x$ відповідає потрібному запису в базі даних, і інше значення $y$ («хибно») для інших значень $x$.

Алгоритм Ґровера також може бути використаний для знаходження медіани і середнього арифметичного числового ряду. Крім того, він може застосовуватися для вирішення NP-повних задач шляхом вичерпного пошуку серед безлічі можливих рішень. Це може спричинити значний приріст швидкості в порівнянні з класичними алгоритмами, хоча і не надаючи «поліноміального рішення» в загальному вигляді. Алгоритм може бути додатково оптимізовано, якщо існує більше, ніж один елемент. що збігається і число збігів відомо заздалегідь.

Налаштування

Розглянемо невпорядовану базу даних з $N$ записів. Алгоритм вимагає $N$-вимірний простір станів ${\mathcal {H}}$, в яких можуть перебувати $n=\lceil log_{2}N\rceil$ кубітів. Розглянемо задачу визначення індексу записи бази даних, який задовольняє деяким заданим критеріям. Нехай $f$ — функція, яка показує всі записи бази даних 0 або 1, де $f(x)=1$ тоді і тільки тоді, коли $x$ відповідає критерію пошуку ($x=\omega$). Ми отримали доступ до цієї функції $f$ у вигляді унітарного оператора $U_{\omega }$ (так званий оракул або пророча машина), що діє в такий спосіб:

${\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0.\end{cases}}$

або коротко,

$U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle$.

Тобто це фазовий оракул (такий, що додає мінус перед поміченими значеннями $x$, а інші залишає без змін). Альтернативне визначення $U_{\omega }$ за допомогою іншого типу оракулу $U_{f}$ може виникнути, якщо ми маємо додатковий кубіт (як у квантовій системі, яка зображена нижче). Операція $U_{f}$ тоді представляє собою:

${\begin{cases}U_{f}|x\rangle |y\rangle =|x\rangle |\neg y\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{f}|x\rangle |y\rangle =|x\rangle |y\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0,\end{cases}}$

або коротко,

$U_{f}|x\rangle |y\rangle =|x\rangle |y\oplus f(x)\rangle .$

Це природний спосіб реалізувати бінарну операцію з використанням методу зворотного обчислення. Зверніть увагу, що якщо додатковий кубіт знаходиться в стані $|-\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}=H|1\rangle$, ми отримаємо наш бажаний оракул $U_{\omega }$ та додатковий кубіт:

${\begin{aligned}U_{f}{\big (}|x\rangle \otimes |-\rangle {\big )}&={\frac {1}{\sqrt {2}}}\left(U_{f}|x\rangle |0\rangle -U_{f}|x\rangle |1\rangle \right)\\&={\frac {1}{\sqrt {2}}}\left(|x\rangle |f(x)\rangle -|x\rangle |1\oplus f(x)\rangle \right)\\&={\begin{cases}{\frac {1}{\sqrt {2}}}\left(|x\rangle |1\rangle -|x\rangle |0\rangle \right)=-|x\rangle \otimes |-\rangle &{\text{if }}f(x)=1,\\{\frac {1}{\sqrt {2}}}\left(|x\rangle |0\rangle -|x\rangle |1\rangle \right)=|x\rangle \otimes |-\rangle &{\text{if }}f(x)=0\end{cases}}\\&=(U_{\omega }|x\rangle )\otimes |-\rangle \end{aligned}}$

Не дивлячись на те, який саме оракул для $f$ нам задано, ми зможемо отримати потрібний $U_{\omega }$.

Робота алгоритму

Етапи роботи алгоритму Ґровера наведено нижче. Позначимо через $|s\rangle$ рівномірну суперпозицію за всіма станами

$|s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .$

Тоді оператор

$U_{s}=2\left|s\right\rangle \left\langle s\right|-I$

вважатимемо за оператор дифузії Ґровера.

Власне алгоритм:

1. Ініціалізуємо стан систем
   $|s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .$
2. Виконуємо наступні «ітерації Ґровера» $r(N)$ раз. Функція $r(N)$ асимптотично є $O({\sqrt {N}})$, як описано нижче.
   1. Застосовуємо оператор $U_{\omega }$.
   2. Застосовуємо оператор $U_{s}$.
3. Вимірюємо отриманий квантовий стан.

Для правильного вибраної кількості ітерацій $r$ результат буде $|\omega \rangle$ з імовірністю, що наближається до 1 при N ≫ 1. Аналіз показує, що $r(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }$.

Перша ітерація

Попереднє спостереження, паралельно з нашим визначенням

$U_{s}=2|s\rangle \langle s|-I,$

є $U_{\omega }$, що може бути виражено альтернативним шляхом:

$U_{\omega }=I-2|\omega \rangle \langle \omega |.$

Іншими словами, обидва перетворення мають перетворення типу Хаусхолдера. Для доказу цього достатньо, щоб перевірити, як $U_{\omega }$ діє на основні стани:

${\begin{aligned}(I-2|\omega \rangle \langle \omega |)|\omega \rangle &=|\omega \rangle -2|\omega \rangle \langle \omega |\omega \rangle =-|\omega \rangle =U_{\omega }|\omega \rangle ,\\(I-2|\omega \rangle \langle \omega |)|x\rangle &=|x\rangle -2|\omega \rangle \langle \omega |x\rangle =|x\rangle =U_{\omega }|x\rangle &&\forall x\neq \omega .\end{aligned}}$

Наступні обчислення показують, що відбувається в першій ітерації::

${\begin{aligned}\langle \omega |s\rangle &=\langle s|\omega \rangle ={\tfrac {1}{\sqrt {N}}},\\\langle s|s\rangle &=N{\tfrac {1}{\sqrt {N}}}\cdot {\tfrac {1}{\sqrt {N}}}=1,\\U_{\omega }|s\rangle &=(I-2|\omega \rangle \langle \omega |)|s\rangle =|s\rangle -2|\omega \rangle \langle \omega |s\rangle =|s\rangle -{\tfrac {2}{\sqrt {N}}}|\omega \rangle ,\\U_{s}\left(|s\rangle -{\tfrac {2}{\sqrt {N}}}|\omega \rangle \right)&=\left(2|s\rangle \langle s|-I\right)\left(|s\rangle -{\tfrac {2}{\sqrt {N}}}|\omega \rangle \right)=2|s\rangle \langle s|s\rangle -|s\rangle -{\tfrac {4}{\sqrt {N}}}|s\rangle \langle s|\omega \rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle \\&=2|s\rangle -|s\rangle -{\tfrac {4}{\sqrt {N}}}\cdot {\tfrac {1}{\sqrt {N}}}|s\rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle =|s\rangle -{\tfrac {4}{N}}|s\rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle \\&={\tfrac {N-4}{N}}|s\rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle .\end{aligned}}$

Варто відзначити окремий випадок при N = 4 з одним визначеним станом. Це $U_{s}U_{w}|s\rangle =|\omega \rangle$ означає, що в одному застосуванні ітератора Ґровера зазначений стан повертається.

Після застосування операторів $U_{\omega }$ і $U_{s}$, квадрат амплітуди запитуваного елемента збільшиться з $\left|\langle \omega |s\rangle \right|^{2}={\tfrac {1}{N}}$ до $\left|\langle \omega |U_{s}U_{\omega }|s\rangle \right|^{2}=\left|{\tfrac {1}{\sqrt {N}}}\cdot {\tfrac {N-4}{N}}+{\tfrac {2}{\sqrt {N}}}\right|^{2}={\tfrac {(3N-4)^{2}}{N^{3}}}=9\left(1-{\tfrac {4}{3N}}\right)^{2}\cdot {\tfrac {1}{N}}$

Зауваження

Припустимо, рівняння (1) має корені. Класичний алгоритм розв'язання такої задачі (лінійний пошук), очевидно, вимагає $O({\tfrac {N}{l}})$ звернень до $f$ для того, щоб вирішити задачу з імовірністю ½. Алгоритм Ґровера дозволяє розв'язати задачу пошуку за час $O({\sqrt {\tfrac {N}{l}}})$, тобто близько до квадратного кореня з класичного, що є величезним прискоренням. Доведено, що Алгоритм Ґровера є оптимальним в таких випадках:

• константу ${\tfrac {\pi }{4}}$ не можна поліпшити.
• більшого квантового прискорення, ніж квадратичне, не можна отримати.

Алгоритм Ґровера є приклад масової задачі, що залежить від оракула. Для більш приватних завдань вдається отримати більше квантове прискорення. Наприклад, алгоритм факторизації Шора дає експонентний виграш у порівнянні з відповідними класичними алгоритмами.

Те, що f задана у вигляді чорного ящика, ніяк не впливає в загальному випадку на складність як квантових, так і класичних алгоритмів. Знання «пристрою» функції f (наприклад, знання задає її схеми з функціональних елементів) в загальному випадку ніяк не може допомогти у вирішенні рівняння (1). Пошук в базі даних співвідноситься зі зверненням функції, яка приймає певне значення, якщо аргумент x відповідає шуканої записи в базі даних.

Оптимізація

Відомо, що алгоритм Ґровера є оптимальним. Тобто, будь-який алгоритм, який отримує доступ до бази даних тільки за допомогою оператора U_ω має застосовувати U_ω принаймні, стільки раз алгоритм Ґровера. Цей результат важливий для розуміння меж квантових обчислень.

Якщо проблема пошуку в Ґровера мала розв'язок з log^c N застосувань U_ω, що означало б, що NP міститься в BQP, шляхом перетворення проблем в NP в пошукових завдань Ґровер-типу. Оптимальність алгоритму Ґровера передбачає (але не доводить), що NP не міститься в BQP.

Число ітерацій для $k$ «помічених» записів, ${\frac {\pi }{4}}{\sqrt {\frac {N}{k}}}$, також є оптимальним.

Застосовність і обмеження

В базах даних, які не представлені в явному вигляді оракул викликається для оцінки елемента по його індексу, при цьому читання елементів повної бази даних один за одним і перетворення його в доступне подання може зайняти набагато більше часу, ніж пошук Ґровера. Для врахування таких ефектів, алгоритм Ґровера можна розглядати як рішення рівняння або задовольняють обмеження. У таких використаннях, оракул є способом перевірити обмеження і не пов'язаний з алгоритмом пошуку. Це поділ, як правило, запобігає алгоритмічній оптимізації, в той час як звичайні алгоритми пошуку часто покладаються на такі оптимізації і уникнути повного перебору. Ці та інші міркування з приводу використання алгоритму Ґровера обговорюються в статті Віамонте, Маркова та Хеєса.

Алгоритми, що використовують схему Ґровера

• Алгоритм пошуку екстремуму цілочисельної функції (P. Hoyer і ін.). Шукається найбільше значення функції $f:\ \{0,1\}^{n}\rightarrow \{0,1\}^{n}$. Квантовий алгоритм знаходить максимум за $O({\sqrt {N}})$ звернень до $f$.
• Алгоритм пошуку співпадаючих рядків в базі даних (Амбайніс). Шукається пара різних аргументів $x_{1}\neq x_{2}$, на яких функція $f:\ \{0,1\}^{n}\rightarrow \{0,1\}^{n}$ приймає одне і те ж значення. Алгоритм вимагає $O(N^{3/4})$ звернень до $f$.

Варіації і узагальнення

Безперервні версії алгоритму Ґровера

• Нехай гамільтоніан квантової системи має вигляд $H=H_{1}+H_{2}$ , де $\exp(iH_{1})$  і  $\exp(iH_{2})$ являють собою оператори $I_{\tilde {0}}$ і $I_{\tilde {0}}$ відповідно. Тоді безперервна унітарна еволюція з гамільтоніаном $H$, починаючи з $|{\tilde {0}}\rangle$, приводить до $|x_{tar}\rangle$. Складність такого безперервного аналога алгоритму Ґровера точно та ж, що і для дискретного випадку.
• Адіабатичний варіант алгоритму Ґровера. Повільна еволюція основного стану типу $|{\tilde {0}}\rangle$ під дією гамільтоніана, залежить від f , згідно адіабатичній теоремі, за час порядку ${\sqrt {N}}$ веде до стану $|x_{tar}\rangle$.

Див. також

• Алгоритм Шора
• Алгоритм з оракулом
• Квантове програмування

Джерела

• Grover L.K.: A fast quantum mechanical algorithm for database search [Архівовано 1 жовтня 2017 у Wayback Machine.], Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
• Grover L.K.: From Schrödinger's equation to quantum search algorithm [Архівовано 11 листопада 2020 у Wayback Machine.], American Journal of Physics, 69(7): 769—777, 2001. Pedagogical review of the algorithm and its history.
• Grover L.K.: QUANTUM COMPUTING: How the weird logic of the subatomic world could make it possible for machines to calculate millions of times faster than they do today [Архівовано 10 березня 2017 у Wayback Machine.] The Sciences, July/August 1999, pp. 24–30.
• Nielsen, M.A. and Chuang, I.L. Quantum computation and quantum information. Cambridge University Press, 2000. Chapter 6.
• What's a Quantum Phone Book?, Lov Grover, Lucent Technologies
• Grover's Algorithm: Quantum Database Search [Архівовано 7 листопада 2021 у Wayback Machine.], C. Lavor, L.R.U. Manssur, R. Portugal
• Grover's algorithm on arxiv.org
• Davy Wybiral. Quantum Circuit Simulator. Архів оригіналу за 16 січня 2017. Процитовано 13 січня 2017.
• Craig Gidney (5 березня 2013). Grover's Quantum Search Algorithm. Архів оригіналу за 17 листопада 2020. Процитовано 15 листопада 2020.
• François Schwarzentruber (18 травня 2013). Grover's algorithm. Архів оригіналу за 16 листопада 2020. Процитовано 15 листопада 2020.
• Alexander Prokopenya. Quantum Circuit Implementing Grover's Search Algorithm. Wolfram Alpha. Архів оригіналу за 20 листопада 2020. Процитовано 15 листопада 2020.
• Hazewinkel, Michiel, ред. (2001), computation, theory of Quantum computation, theory of, Математична енциклопедія, Springer, ISBN 978-1-55608-010-4
• Roberto Maestre (11 травня 2018). Grover's Algorithm implemented in R and C. Архів оригіналу за 17 жовтня 2021. Процитовано 15 листопада 2020.